struct MergeSortIterator<T: Ord + Clone> {  
    data: Vec<T>,  
    // TODO: 添加迭代状态字段  
    index: usize,
}  

// 添加结构体专属实现块
impl<T: Ord + Clone> MergeSortIterator<T> {
    fn new(data: Vec<T>) -> Self {
        Self { data, index: 0 }
    }
}

impl<T: Ord + Clone> Iterator for MergeSortIterator<T> {  
    type Item = T;  
    fn next(&mut self) -> Option<Self::Item> {  
        // TODO: 归并排序逻辑  
        if self.index == 0 && self.data.len() > 1 {
            self.data = merge_sort(&self.data);
        }
        if self.index < self.data.len() {
            let item = self.data[self.index].clone();
            self.index += 1;
            Some(item)
        } else {
            None
        }  
    }  
}  

fn merge_sort<T: Ord + Clone>(vec: &[T]) -> Vec<T> {
    if vec.len() <= 1 {
        return vec.to_vec();
    }
    let mid = vec.len() / 2;
    let left = merge_sort(&vec[0..mid]);
    let right = merge_sort(&vec[mid..]);
    merge(&left, &right)
}

fn merge<T: Ord + Clone>(left: &[T], right: &[T]) -> Vec<T> {
    let mut result = Vec::with_capacity(left.len() + right.len());
    let (mut i, mut j) = (0, 0);
    while i < left.len() && j < right.len() {
        if left[i] <= right[j] {
            result.push(left[i].clone());
            i += 1;
        } else {
            result.push(right[j].clone());
            j += 1;
        }
    }
    result.extend_from_slice(&left[i..]);
    result.extend_from_slice(&right[j..]);
    result
}

#[test]  
fn test_merge_sort_iter() {  
    let data = vec![5, 3, 4, 1, 2];  
    //let sorted: Vec<_> = MergeSortIterator { data }.collect();  
    let sorted: Vec<_> = MergeSortIterator::new(data).collect(); 
    assert_eq!(sorted, vec![1, 2, 3, 4, 5]);  
}  

fn main() {
    // 演示1：基础整数排序
    let data1 = vec![5, 3, 4, 1, 2];
    let sorted1: Vec<_> = MergeSortIterator::new(data1.clone()).collect();
    println!("\n\x1b[36m=== 基础演示 ===\x1b[0m");
    println!("原始数据: {:?}", data1);
    println!("排序结果: {:?}", sorted1);

    // 演示2：字符串排序
    let data2 = vec!["Rust", "C++", "Python", "Java"];
    let sorted2: Vec<_> = MergeSortIterator::new(data2.clone()).collect();
    println!("\n\x1b[36m=== 字符串排序 ===\x1b[0m");
    println!("原始数据: {:?}", data2);
    println!("排序结果: {:?}", sorted2);

    // 演示3：边界测试
    let edge_cases = vec![
        vec![],                          // 空数组
        vec![42],                       // 单元素
        vec![3, 1],                     // 两元素
        vec![9, 8, 7, 6, 5, 4, 3, 2, 1],// 逆序
    ];

    println!("\n\x1b[36m=== 边界测试 ===\x1b[0m");
    for (i, case) in edge_cases.iter().enumerate() {
        let sorted = MergeSortIterator::new(case.clone()).collect::<Vec<_>>();
        println!("测试 {}: 输入{:?} => 输出{:?}", i+1, case, sorted);
    }

    // 性能演示
    println!("\n\x1b[36m=== 性能提示 ===\x1b[0m");
    let big_data = (0..1000).rev().collect::<Vec<i32>>();
    println!("正在排序1000个元素...");
    let start = std::time::Instant::now();
    let _ = MergeSortIterator::new(big_data).collect::<Vec<_>>();
    let duration = start.elapsed();
    println!("排序耗时: {:.2?}", duration);
}